0Мiнiстерство освiти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Курсова робота(Частина 2) з дисципліни «Програмування. Частина ІІІ. Структури даних та алгоритми»
Вибір варіанту:
Вибір АТД: (6+5+77)%3+1=2
Вибір номера завдання: (6+77)%10+1=4
Зміст
Завдання 2: Динамічні структури даних----------------------------------------------------------3
2.1. Теоретична частина----------------------------------------------------------------------------4
2.2. Частина 1. Побудова АТД-------------------------------------------------------------------9
2.2.1. Постановка задачі------------------------------------------------------------------------9
2.2.2. Динаміка вмісту--------------------------------------------------------------------------9
2.2.3. Результати виконання програми-----------------------------------------------------11
2.3. Частина 2. Застосування АТД-------------------------------------------------------------12
2.3.1. Постановка задачі-----------------------------------------------------------------------12
2.3.2. Алгоритм розв’язання задачі---------------------------------------------------------12
2.3.3. Результати виконання програми-----------------------------------------------------13
Висновки-------------------------------------------------------------------------------------------------14
Список літератури-------------------------------------------------------------------------------------15
Додатки---------------------------------------------------------------------------------------------------16
Завдання 2. Частина 1: Побудова АТД
Змоделювати абстрактний тип даних (АТД) на базі статичного масиву, який використати в другій частині цього завдання. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів в АТД. Для реалізації цього задати послідовність з К > 10 цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в АТД, а кожне непарне число має вилучати з АТД один елемент. Виводити на екран динаміку вмісту АТД під час обробки заданої послідовності.
Завдання 2. Частина 2: Застосування АТД
Розв’язати задачу використовуючи АТД "ЧЕРГА"
Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow).
Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами.
Змоделювати чергу, в якій до опису черги додано функцію wipe_out, яка вилучає всі елементи з черги. Кожний раз, коли у вхідній послідовності зустрічається число 0, то всі елементи мають бути вилучені з черги. Після обробки всієї заданої вхідної послідовності перевірити, чи є в черзі одинакові числа.
2.1. Теоретична частина
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип ...
